Many of the tasks that are addressed by decision-making systems and artificial intelligence systems can be represented as constraint satisfaction problems (“CSP”s). In this representation, the task is specified in terms of a set of variables, each of which can assume values in a given domain, and a set of constraints that the variables must simultaneously satisfy. The set of variables, domains and constraints is referred to as a CSP. Each constraint may be expressed as a relation, defined over some subset of the variables, denoting valid combinations of their values. A solution to a CSP is an assignment of a value to all the variables from their respective domains that satisfies all of the constraints.
A constraint based system includes a constraint solver that attempts to find one or more solutions to a given CSP, or prove that no solution exists. Constraint based systems are used for many artificial intelligence related applications and a variety of other applications, including: (1) Product configurators; (2) Robotic control; (3) Temporal reasoning; (4) Natural language processing; (5) Spatial reasoning; (6) Test-case generation for software and hardware systems; (7) Machine vision; (8) Medical diagnosis; (9) Resource allocation; and (10) Frequency allocation.
The network of constraints in a CSP can be viewed as a graph, having a node for each variable and an “arc” for each constraint. The members of each arc are the variables that appear in the constraint to which the arc corresponds. An arc is said to be consistent if for any variable of the arc, and any value in the domain of the variable, there is a valid assignment of values to the other variables on the arc that satisfies the constraint represented by the arc.
Some known constraint based systems allow a user to interact with a computer interface in order to customize and configure a solution by selecting among optional choices and making user decisions. For these systems, constraints are enforced between optional choices, allowing the user to select the choices they want, while validating that the resulting set of user decisions is valid. Some of these known systems are not fully “interactive” because they function as batch systems in which all of the user decisions are initially collected and then checked for validity as a batch. Other known systems, when receiving a user decision, propagate the user decision through its constraint network. However, a conflict due to the propagation will likely cause a removal of some of the prior selections and will likely require a restart of the entire configuration process. This causes the user to have to essentially start over, or at a minimum slows down the processing, thus diminishing the interactive experience.